#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<limits.h>

int maxSubArray(int* arr, int left, int right);

int main() {
    int arr[] = { -2,3,-2,4,-1,2,1,-5,4 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    int left = 0;
    int ret = maxSubArray(arr, left, sz - 1);
    printf("%d\n", ret);
    return 0;
}

int maxSubArray(int* arr, int left, int right) {
    int leftsum, rightsum;
    int leftmax, rightmax;
    int mid, i, leftmidsum, rightmidsum;

    if (left == right) {
        return arr[left];
    }

    mid = (left + right) >>1;

    leftsum = maxSubArray(arr, left, mid);
    rightsum = maxSubArray(arr, mid + 1, right);

    leftmidsum = 0;
    leftmax = INT_MIN;
    for (i = mid; i >= left; i--) {  //-2,3,-2,4,-1,2,1,-5,4;
        leftmidsum += arr[i];
        if (leftmidsum > leftmax)
            leftmax = leftmidsum;
    }

    rightmidsum = 0;
    rightmax = INT_MIN;
    for (i = mid + 1; i <= right; i++) {
        rightmidsum += arr[i];
        if (rightmidsum > rightmax)
            rightmax = rightmidsum;
    }
    int polarmax = (leftsum > rightsum) ? leftsum : rightsum;
    int bordermax = leftmax + rightmax;

    return (bordermax > polarmax) ? bordermax : polarmax;
}
